Part I Multivariate normal distribution
Let \(\boldsymbol{x} = (x_1, \dots, x_n), n = 100\) be multivariate normal distributed with \(E(x_i) = 0, Var(x_i) = 1\), and \(Corr(x_i, x_j) = e^{-0.1|i - j|}\)
Compute and image the covariance matrix \(\boldsymbol{\Sigma}\) of \(\boldsymbol{x}\)
Find the lower Cholesky factor \(\boldsymbol{L}\), such that \(\boldsymbol{L}\boldsymbol{L}^T = \boldsymbol{\Sigma}\), of this covariance matrix, and image.
Sample \(\boldsymbol{x} = \boldsymbol{Lz}\), where \(\boldsymbol{z}\) is a length n random vector of independent standard normal variables. Plot the sample.
Find the precision matrix \(\boldsymbol{Q}\) of the covariance matrix, and compute the lower Cholesky factor \(\boldsymbol{L}_Q\), such that \(\boldsymbol{L}_Q\boldsymbol{L}_Q^T = \boldsymbol{Q}\), of this matrix. Image these matrices and compare them to the images obtained in a) and b)
Sample \(\boldsymbol{x}\) by solving \(\boldsymbol{L}_Q^T\boldsymbol{x} = \boldsymbol{z}\), where \(\boldsymbol{z}\) is a length n random vector of independen standard normal variables. Plot the sample.
Permute the ordering of variables in \(\boldsymbol{x}\), and redo the exercises.
Solution to Part I
a)
Given that \(\boldsymbol{\Sigma} = e^{-0.1|i - j|}\). The covariance matrix can be expressed as follows: \[\begin{equation*}
\Sigma = \begin{pmatrix}
1 & e^{- 0.1 h_{12}} &\dots & e^{- 0.1 h_{1n}} \\
e^{- 0.1 h_{21}} & 1 & \dots & e^{- 0.1 h_{2n}} \\
\vdots & \vdots & \ddots & \vdots \\
e^{- 0.1 h_{n1}} & e^{- 0.1 h_{n2}} & \dots & 1
\end{pmatrix}
\end{equation*}\]
### b) According to the cholesky decomposition rule, \(\boldsymbol{L}\) is the lower triangular matrix for \(\boldsymbol{\Sigma}\), it can be easily computed from R using L = chol(Sigma). It is then plotted as below.

c)
Sample using \(\boldsymbol{x} = \boldsymbol{L}\boldsymbol{z}\) transforms the zero-mean, standard normal random variales to the random variables with the desired covariance matrix.

e)
Similarly, the expected random samples can be generated using the inversion of the above formula, thus \(\boldsymbol{L}_Q^T\boldsymbol{x} = \boldsymbol{z}\)

Part II Gaussian random fields and Kriging
The purpose of this computer exercise is to give an introduction to parameter estima- tion and kriging for Gaussian random field models for spatial data.
We assume the following observation model on the unit square:
\[\begin{equation*}
y(\boldsymbol{s}_j) = x(\boldsymbol{s}_j) + \epsilon_j, \ \ \ j = 1, \dots, N,
\end{equation*}\]
where \(\epsilon_j ~ \mathop{N}(0, \tau^2)\) are independent measurement noise terms. Further, consider a Matérn covariance function for the Gaussian random field \(\boldsymbol{x(s)}\):
\[\begin{equation*}
Cov(x(\boldsymbol{s}_i), x(\boldsymbol{s}_j)) = \Sigma_{i, j} = \sigma^2(1 + \phi h)\exp(-\phi h),
\end{equation*}\]
where \(h\) denotes the Euclidean distance between the two sites \(\boldsymbol{s}_i\) and \(\boldsymbol{s}_j\).
We assume the mean increases with east and north coordinates as follows: \(\mu_j = \alpha((s_{j1} - 0.5) + (s_{j2} - 0.5))\), for site \(\boldsymbol{s}_j = (s_{j1}, s_{j2})\) on the unit square.
2.2 Paramter estimation
We will now use the simulated data to estimate the model parameters \(\alpha, \sigma^2, \tau^2, \phi\) using maximum likelihood estimation. Iterate between the update for the mean parameter, and updating the covariance parameters. Monitor the likelihood function at each step of the algorithm to check convergence.
## [1] "0.895765013504915 , iter no is 0"
## [1] "0.304910507162466 , iter no is 1"
## [1] "0.270287466981051 , iter no is 2"
## [1] "0.222351840261664 , iter no is 3"
## [1] "0.202516701628354 , iter no is 4"

##
## Estimated sigma is 1.125 ; True sigma is 1
## Estimated phi is 10.54 ; True phi is 10
## Estimated tau is 0.01016 ; True tau is 0.05
## Estimated beta1 is -0.93 ; True beta1 is -1
## Estimated beta2 is 1.34 ; True beta2 is 1
## Estimated beta3 is 0.92 ; True beta3 is 1NULL
2.3 Kriging
We will now use the estimated model parameters to perform kriging prediction. Predict variables \(x(s)\), where predictions sites lie on a regular grid of size 25x25 for the unit square. Visualize the Kriging surface and the prediction standard error. Compare with the true field.


## [1] "The prediction error is 1.93020697440398"
LS0tCnRpdGxlOiAiUHJvamVjdDIiCnN1YnRpdGxlOiAiR2F1c3NpYW4gcmFuZG9tIGZpZWxkIHdpdGggYXBwbGljYXRpb24gb2YgSU5MQSIKYXV0aG9yOiAkXG92ZXJzZXR7XG1hdGhybXt5YW9saW4uZ2VAbnRudS5ub319ezEwMDI2fSQgXGFuZAogICAgICAgICRcb3ZlcnNldHtcbWF0aHJte3lhb2xpbi5nZUBudG51Lm5vfX17MTAwMjZ9JApvdXRwdXQ6CiAgIyBwZGZfZG9jdW1lbnQ6CiAgIyAgIHRvYzogdHJ1ZQogICMgICB0b2NfZGVwdGg6IDMKICAjICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6IHllcwogICAgY29kZV9kb3dubG9hZDogeWVzCiAgICB0b2NfZGVwdGg6IDMKICBpb3NsaWRlc19wcmVzZW50YXRpb246IGRlZmF1bHQKICBiZWFtZXJfcHJlc2VudGF0aW9uOgogICAgc2xpZGVfbGV2ZWw6IDEKICAgIGtlZXBfdGV4OiB5ZXMKICBwZGZfZG9jdW1lbnQ6CiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiAyCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9VFJVRSxlY2hvPUZBTFNFfQpzdXBwcmVzc1BhY2thZ2VTdGFydHVwTWVzc2FnZXMobGlicmFyeShrbml0cikpCmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gRkFMU0UsIG1lc3NhZ2U9RkFMU0Usd2FybmluZyA9IEZBTFNFLCBlcnJvciA9IEZBTFNFKQpgYGAKCmBgYHtyIGxvYWQgbGlicmFyaWVzLCBlY2hvID0gRn0KbGlicmFyeShsYXR0aWNlKQpsaWJyYXJ5KHZpcmlkaXNMaXRlKQpjb3VsIDwtIHZpcmlkaXMoMTAwKQpgYGAKCiMgUGFydCBJIE11bHRpdmFyaWF0ZSBub3JtYWwgZGlzdHJpYnV0aW9uCkxldCAkXGJvbGRzeW1ib2x7eH0gPSAoeF8xLCBcZG90cywgeF9uKSwgbiA9IDEwMCQgYmUgbXVsdGl2YXJpYXRlIG5vcm1hbCBkaXN0cmlidXRlZCB3aXRoICRFKHhfaSkgPSAwLCBWYXIoeF9pKSA9IDEkLCBhbmQgJENvcnIoeF9pLCB4X2opID0gZV57LTAuMXxpIC0ganx9JAoKYSkgQ29tcHV0ZSBhbmQgaW1hZ2UgdGhlIGNvdmFyaWFuY2UgbWF0cml4ICRcYm9sZHN5bWJvbHtcU2lnbWF9JCBvZiAkXGJvbGRzeW1ib2x7eH0kCgpiKSBGaW5kIHRoZSBsb3dlciBDaG9sZXNreSBmYWN0b3IgJFxib2xkc3ltYm9se0x9JCwgc3VjaCB0aGF0ICRcYm9sZHN5bWJvbHtMfVxib2xkc3ltYm9se0x9XlQgPSBcYm9sZHN5bWJvbHtcU2lnbWF9JCwgb2YgdGhpcyBjb3ZhcmlhbmNlIG1hdHJpeCwgYW5kIGltYWdlLgoKYykgU2FtcGxlICRcYm9sZHN5bWJvbHt4fSA9IFxib2xkc3ltYm9se0x6fSQsIHdoZXJlICRcYm9sZHN5bWJvbHt6fSQgaXMgYSBsZW5ndGggbiByYW5kb20gdmVjdG9yIG9mIGluZGVwZW5kZW50IHN0YW5kYXJkIG5vcm1hbCB2YXJpYWJsZXMuIFBsb3QgdGhlIHNhbXBsZS4KCmQpIEZpbmQgdGhlIHByZWNpc2lvbiBtYXRyaXggJFxib2xkc3ltYm9se1F9JCBvZiB0aGUgY292YXJpYW5jZSBtYXRyaXgsIGFuZCBjb21wdXRlIHRoZSBsb3dlciBDaG9sZXNreSBmYWN0b3IgJFxib2xkc3ltYm9se0x9X1EkLCBzdWNoIHRoYXQgJFxib2xkc3ltYm9se0x9X1FcYm9sZHN5bWJvbHtMfV9RXlQgPSBcYm9sZHN5bWJvbHtRfSQsIG9mIHRoaXMgbWF0cml4LiBJbWFnZSB0aGVzZSBtYXRyaWNlcyBhbmQgY29tcGFyZSB0aGVtIHRvIHRoZSBpbWFnZXMgb2J0YWluZWQgaW4gYSkgYW5kIGIpCgplKSBTYW1wbGUgJFxib2xkc3ltYm9se3h9JCBieSBzb2x2aW5nICRcYm9sZHN5bWJvbHtMfV9RXlRcYm9sZHN5bWJvbHt4fSA9IFxib2xkc3ltYm9se3p9JCwgd2hlcmUgJFxib2xkc3ltYm9se3p9JCBpcyBhIGxlbmd0aCBuIHJhbmRvbSB2ZWN0b3Igb2YgaW5kZXBlbmRlbiBzdGFuZGFyZCBub3JtYWwgdmFyaWFibGVzLiBQbG90IHRoZSBzYW1wbGUuCgpmKSBQZXJtdXRlIHRoZSBvcmRlcmluZyBvZiB2YXJpYWJsZXMgaW4gJFxib2xkc3ltYm9se3h9JCwgYW5kIHJlZG8gdGhlIGV4ZXJjaXNlcy4gCgoKKioqCgojIyBTb2x1dGlvbiB0byBQYXJ0IEkKCiMjIyBhKSAKR2l2ZW4gdGhhdCAkXGJvbGRzeW1ib2x7XFNpZ21hfSA9IGVeey0wLjF8aSAtIGp8fSQuIFRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBjYW4gYmUgZXhwcmVzc2VkIGFzIGZvbGxvd3M6ClxiZWdpbntlcXVhdGlvbip9CiAgICBcU2lnbWEgPSBcYmVnaW57cG1hdHJpeH0gCiAgICAxICYgIGVeey0gMC4xIGhfezEyfX0gJlxkb3RzICYgZV57LSAwLjEgaF97MW59fSBcXAogICAgZV57LSAwLjEgaF97MjF9fSAmIDEgJiBcZG90cyAmIGVeey0gMC4xIGhfezJufX0gXFwKICAgIFx2ZG90cyAmIFx2ZG90cyAmIFxkZG90cyAmIFx2ZG90cyBcXAogICAgZV57LSAwLjEgaF97bjF9fSAmIGVeey0gMC4xIGhfe24yfX0gJiBcZG90cyAmIDEKICAgIFxlbmR7cG1hdHJpeH0KXGVuZHtlcXVhdGlvbip9CgpgYGB7ciBjb3ZhcmlhbmNlIG1hdHJpeCwgZWNobyA9IEYsIGZpZy5hbGlnbj0nY2VudGVyJ30KIyBzaXplcwpuIDwtIDEwMAoKIyBkZWZpbmUgcmVndWxhciBncmlkIG9mIGxvY2F0aW9ucwpzaXRlczF2IDwtIGFycmF5KCgxOm4pLGMobiwxKSkKCiMgUHJpb3IgbWVhbgptIDwtIDAKIyBjb21wdXRlIEVhc3QgYW5kIE5vcnRoIGRpc3RhbmNlcyBvbiBncmlkCnd3IDwtIGFycmF5KDEsYyhuLDEpKQoKIyBkZXRlcm1pbmUgdGhlIGRpc3RhbmNlIG1hdHJpeApIIDwtIGFicyhzaXRlczF2JSoldCh3dyktd3cgJSolIHQoc2l0ZXMxdikpCgojIEV4cG9uZW50aWFsIGNvdmFyaWFuY2UgbW9kZWwKU2lnbWEgPC0gZXhwKC0wLjEqSCkKCiMgUGxvdCB0aGUgY292YXJpYW5jZSBtYXRyaXgKbGV2ZWxwbG90KFNpZ21hLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiQ292YXJpYW5jZSBtYXRyaXgiKQpgYGAKIyMjIGIpIApBY2NvcmRpbmcgdG8gdGhlIGNob2xlc2t5IGRlY29tcG9zaXRpb24gcnVsZSwgJFxib2xkc3ltYm9se0x9JCBpcyB0aGUgbG93ZXIgdHJpYW5ndWxhciBtYXRyaXggZm9yICRcYm9sZHN5bWJvbHtcU2lnbWF9JCwgaXQgY2FuIGJlIGVhc2lseSBjb21wdXRlZCBmcm9tIFIgdXNpbmcgYEwgPSBjaG9sKFNpZ21hKWAuIEl0IGlzIHRoZW4gcGxvdHRlZCBhcyBiZWxvdy4gCgpgYGB7ciBDaG9sZXNreSwgZWNobyA9IEYsIGZpZy5hbGlnbj0nY2VudGVyJ30KTCA8LSBjaG9sKFNpZ21hKQpsZXZlbHBsb3QoTCwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgbWF0cml4IikKYGBgCgoKIyMjIGMpIApTYW1wbGUgdXNpbmcgJFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7TH1cYm9sZHN5bWJvbHt6fSQgdHJhbnNmb3JtcyB0aGUgemVyby1tZWFuLCBzdGFuZGFyZCBub3JtYWwgcmFuZG9tIHZhcmlhbGVzIHRvIHRoZSByYW5kb20gdmFyaWFibGVzIHdpdGggdGhlIGRlc2lyZWQgY292YXJpYW5jZSBtYXRyaXguIAoKYGBge3IsIHJhbmRvbSBzYW1wbGVzLCBmaWcuYWxpZ249J2NlbnRlcid9CnogPSBybm9ybSgxMDApCnggPSBMICUqJSB6CnBsb3QoeCwgbWFpbiA9ICJSYW5kb20gc2FtcGxlcyBnaXZlbiB0aGUgY292YXJpYW5jZSIpCmBgYAoKCiMjIyBkKSAKVGhlIHByZWNpc2lvbiBtYXRyaXggJFxib2xkc3ltYm9se1F9JCBpcyB0aGUgaW52ZXJzZSBvZiB0aGUgY292YXJpYW5jZSBtYXRyaXggJFxib2xkc3ltYm9se1xTaWdtYX0kLCBpdCBpcyBjb21wdXRlZCB1c2luZyBgUSA9IHNvbHZlKFNpZ21hKWAgaW4gUi4gVGhlIHRocmVlIG1hdHJpY2VzIGFyZSB0aGVyZWJ5IGRlcGljdGVkIGFzIGZvbGxvd3MuIFNpbmNlIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBpcyBub3Qgc2luZ3VsYXIsIGdpdmVuIHRoYXQgdGhlIGl0IGJlbG9uZ3MgdG8gdGhlIE1hdGVybiBmYW1pbHksIHRodXMgaXQgaXMgYW5hbHl0aWNhbGx5IGd1YXJhbnRlZWQgdG8gaGF2ZSBwb3NpdGl2ZSBkZWZpbml0ZSBwcm9wZXJ0eS4gVGhlcmVmb3JlLCBib3RoIHByZWNpc2lvbiBtYXRyaXggYW5kIHRoZSBsb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXggZXhpc3QuIAoKYGBge3IgY29tcCBiZXR3ZWVuIHRocmVlIG1hdHJpY2VzLCBmaWcuc2hvdyA9ICJob2xkIiwgb3V0LndpZHRoPSI1MCUifQpRIDwtIHNvbHZlKFNpZ21hKQpMUSA8LSBjaG9sKFEpCnBhcihtYXIgPSBjKDQsNCwuMSwgLjEpKQojIHBhcihtZnJvdz1jKDEsMyksIG1hcj1jKDQsNCw0LDEpLCBvbWE9YygwLjUsMC41LDAuNSwwKSkKbGV2ZWxwbG90KFNpZ21hLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiQ292YXJpYW5jZSBtYXRyaXgiKQpsZXZlbHBsb3QoTCwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgY292YXJpYW5jZSBtYXRyaXgiKQpsZXZlbHBsb3QoUSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIlByZWNpc2lvbiBtYXRyaXgiKQpsZXZlbHBsb3QoTFEsIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9ICJMb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXgiKQojIGxldmVscGxvdChMUSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgbWF0cml4IikKYGBgCgoKIyMjIGUpIApTaW1pbGFybHksIHRoZSBleHBlY3RlZCByYW5kb20gc2FtcGxlcyBjYW4gYmUgZ2VuZXJhdGVkIHVzaW5nIHRoZSBpbnZlcnNpb24gb2YgdGhlIGFib3ZlIGZvcm11bGEsIHRodXMgJFxib2xkc3ltYm9se0x9X1FeVFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7en0kCgpgYGB7ciwgc2FtcGxlIGluIGludmVyc2lvbiB3YXksIGZpZy5hbGlnbj0nY2VudGVyJ30KeiA9IHJub3JtKDEwMCkKeCA9IHNvbHZlKHQoTFEpLCB6KQpwbG90KHgsIG1haW4gPSAiUmFuZG9tIHNhbXBsZXMgdXNpbmcgaW52ZXJzaW9uIHJ1bGUiKQpgYGAKCiMjIyBmKSAKUGVybXV0ZSAkXGJvbGRzeW1ib2x7eH0kIHRvIG1ha2UgcmFuZG9taXNlIHRoZSBvcmRlcmluZyBvZiB0aGUgZ3JpZCwgdGhlIGFzc2NvY2lhdGVkIGNvdmFyaWFuY2UgbWF0cml4IGNhbiBiZSB0aGVyZWJ5IG1vZGlmaWVkIGluIGEgc3BhcnNlIHdheS4gCgpgYGB7ciwgcGVybXV0YXRpb24sIGZpZy5hbGlnbj0nY2VudGVyJ30Kbl9wZXIgPSAzClNpZ21hX3BlciA8LSBsaXN0KCkKTF9wZXIgPC0gbGlzdCgpClFfcGVyIDwtIGxpc3QoKQpMUV9wZXIgPC0gbGlzdCgpCmZvciAoaSBpbiBjKDE6bl9wZXIpKXsKICBzaXRlczF2X3BlciA8LSBhcnJheShzYW1wbGUoc2l0ZXMxdiwgc2l6ZSA9IG4sIHJlcGxhY2UgPSBGQUxTRSksIGMobiwxKSkKICAjIGRldGVybWluZSB0aGUgZGlzdGFuY2UgbWF0cml4CiAgSF9wZXIgPC0gYWJzKHNpdGVzMXZfcGVyJSoldCh3dyktd3cgJSolIHQoc2l0ZXMxdl9wZXIpKQogICMgRXhwb25lbnRpYWwgY292YXJpYW5jZSBtb2RlbAogIFNpZ21hX3RlbXAgPC0gZXhwKC0wLjEqSF9wZXIpCiAgU2lnbWFfcGVyW1tpXV0gPC0gU2lnbWFfdGVtcAogICMgTCBtYXRyaXgKICBMX3RlbXAgPC0gY2hvbChTaWdtYV90ZW1wKQogIExfcGVyW1tpXV0gPC0gTF90ZW1wCiAgCiAgeiA9IHJub3JtKDEwMCkKICB4X3BlciA9IExfdGVtcCAlKiUgegogIHBsb3QoeF9wZXIsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgcmFuZG9tIHNhbXBsZXMgZ2l2ZW4gdGhlIGNvdmFyaWFuY2UiKSkKICAKICBRX3RlbXAgPC0gc29sdmUoU2lnbWFfdGVtcCkKICBMUV90ZW1wIDwtIGNob2woUV90ZW1wKQogIFFfcGVyW1tpXV0gPC0gUV90ZW1wCiAgTFFfcGVyW1tpXV0gPC0gTFFfdGVtcAogIHogPSBybm9ybSgxMDApCiAgeF9wZXIgPSBzb2x2ZSh0KExRX3RlbXApLCB6KQogIHBsb3QoeF9wZXIsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgcmFuZG9tIHNhbXBsZXMgdXNpbmcgaW52ZXJzaW9uIHJ1bGUiKSkKfQoKCmBgYAoKYGBge3IsIGNvbnQgcGxvdHRpbmcgMSwgZmlnLnNob3cgPSAiaG9sZCIsIG91dC53aWR0aD0iNTAlIn0KaSA9IDEKcGFyKG1hciA9IGMoNCwgNCwuMSwgLjEpKQojIHBhcihtZnJvdz1jKDEsMyksIG1hcj1jKDQsNCw0LDEpLCBvbWE9YygwLjUsMC41LDAuNSwwKSkKbGV2ZWxwbG90KFNpZ21hX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgY292YXJpYW5jZSBtYXRyaXgiKSkKbGV2ZWxwbG90KExfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIGxvd2VyIHRyaWFuZ3VsYXIgY292YXJpYW5jZSBtYXRyaXgiKSkKbGV2ZWxwbG90KFFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIHByZWNpc2lvbiBtYXRyaXgiKSkKbGV2ZWxwbG90KExRX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBsb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXgiKSkKYGBgCgpgYGB7ciwgY29udCBwbG90dGluZyAyLCBmaWcuc2hvdyA9ICJob2xkIiwgb3V0LndpZHRoPSI1MCUifQppID0gMgpwYXIobWFyID0gYyg0LCA0LC4xLCAuMSkpCiMgcGFyKG1mcm93PWMoMSwzKSwgbWFyPWMoNCw0LDQsMSksIG9tYT1jKDAuNSwwLjUsMC41LDApKQpsZXZlbHBsb3QoU2lnbWFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksICJQZXJtdXRlZCBjb3ZhcmlhbmNlIG1hdHJpeCIpKQpsZXZlbHBsb3QoTF9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgbG93ZXIgdHJpYW5ndWxhciBjb3ZhcmlhbmNlIG1hdHJpeCIpKQpsZXZlbHBsb3QoUV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgcHJlY2lzaW9uIG1hdHJpeCIpKQpsZXZlbHBsb3QoTFFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIGxvd2VyIHRyaWFuZ3VsYXIgcHJlY2lzaW9uIG1hdHJpeCIpKQpgYGAKCmBgYHtyLCBjb250IHBsb3R0aW5nIDMsIGZpZy5zaG93ID0gImhvbGQiLCBvdXQud2lkdGg9IjUwJSJ9CmkgPSAzCnBhcihtYXIgPSBjKDQsIDQsLjEsIC4xKSkKIyBwYXIobWZyb3c9YygxLDMpLCBtYXI9Yyg0LDQsNCwxKSwgb21hPWMoMC41LDAuNSwwLjUsMCkpCmxldmVscGxvdChTaWdtYV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwgIlBlcm11dGVkIGNvdmFyaWFuY2UgbWF0cml4IikpCmxldmVscGxvdChMX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBsb3dlciB0cmlhbmd1bGFyIGNvdmFyaWFuY2UgbWF0cml4IikpCmxldmVscGxvdChRX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBwcmVjaXNpb24gbWF0cml4IikpCmxldmVscGxvdChMUV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgbG93ZXIgdHJpYW5ndWxhciBwcmVjaXNpb24gbWF0cml4IikpCmBgYAoKCgojIFBhcnQgSUkgR2F1c3NpYW4gcmFuZG9tIGZpZWxkcyBhbmQgS3JpZ2luZwoKVGhlIHB1cnBvc2Ugb2YgdGhpcyBjb21wdXRlciBleGVyY2lzZSBpcyB0byBnaXZlIGFuIGludHJvZHVjdGlvbiB0byBwYXJhbWV0ZXIgZXN0aW1hLSB0aW9uIGFuZCBrcmlnaW5nIGZvciBHYXVzc2lhbiByYW5kb20gZmllbGQgbW9kZWxzIGZvciBzcGF0aWFsIGRhdGEuCgpXZSBhc3N1bWUgdGhlIGZvbGxvd2luZyBvYnNlcnZhdGlvbiBtb2RlbCBvbiB0aGUgdW5pdCBzcXVhcmU6CgpcYmVnaW57ZXF1YXRpb24qfQogICAgeShcYm9sZHN5bWJvbHtzfV9qKSA9IHgoXGJvbGRzeW1ib2x7c31faikgKyBcZXBzaWxvbl9qLCBcIFwgXCAgaiA9IDEsIFxkb3RzLCBOLApcZW5ke2VxdWF0aW9uKn0KCndoZXJlICRcZXBzaWxvbl9qIH4gXG1hdGhvcHtOfSgwLCBcdGF1XjIpJCBhcmUgaW5kZXBlbmRlbnQgbWVhc3VyZW1lbnQgbm9pc2UgdGVybXMuIEZ1cnRoZXIsIGNvbnNpZGVyIGEgTWF0w6lybiBjb3ZhcmlhbmNlIGZ1bmN0aW9uIGZvciB0aGUgR2F1c3NpYW4gcmFuZG9tIGZpZWxkICRcYm9sZHN5bWJvbHt4KHMpfSQ6CgpcYmVnaW57ZXF1YXRpb24qfQogICAgQ292KHgoXGJvbGRzeW1ib2x7c31faSksIHgoXGJvbGRzeW1ib2x7c31faikpID0gXFNpZ21hX3tpLCBqfSA9IFxzaWdtYV4yKDEgKyBccGhpIGgpXGV4cCgtXHBoaSBoKSwKXGVuZHtlcXVhdGlvbip9Cgp3aGVyZSAkaCQgZGVub3RlcyB0aGUgRXVjbGlkZWFuIGRpc3RhbmNlIGJldHdlZW4gdGhlIHR3byBzaXRlcyAkXGJvbGRzeW1ib2x7c31faSQgYW5kICRcYm9sZHN5bWJvbHtzfV9qJC4KCldlIGFzc3VtZSB0aGUgbWVhbiBpbmNyZWFzZXMgd2l0aCBlYXN0IGFuZCBub3J0aCBjb29yZGluYXRlcyBhcyBmb2xsb3dzOiAkXG11X2ogPSBcYWxwaGEoKHNfe2oxfSAtIDAuNSkgKyAoc197ajJ9IC0gMC41KSkkLCBmb3Igc2l0ZSAkXGJvbGRzeW1ib2x7c31faiA9IChzX3tqMX0sIHNfe2oyfSkkIG9uIHRoZSB1bml0IHNxdWFyZS4gCgoqKiogCgojIyAyLjEgU2ltdWxhdGlvbgoKU2ltdWxhdGUgJE4gPSAyMDAkIHJhbmRvbSBzaXRlcyBpbiB0aGUgdW5pdCBzcXVhcmUgYW5kIHBsb3QgdGhlbS4gRm9ybSB0aGUgY292YXJpYW5jZSBtYXRyaXggdXNpbmcgJFxzaWdtYSA9IDEsIFxwaGkgPSAxMCwgXHRhdSA9IDAuMDUkLiBUYWtlIGl0cyBDaG9sZXNreSBkZWNvbXBvc2l0aW9uIGFuZCBzaW11bGF0ZSBkZXBlbmRlbnQgemVyby1tZWFuIEdhdXNzaWFuIGRhdGEgdmFyaWFibGVzLCB0aGVuIGFkZCB0aGUgbWVhbiB1c2luZyAkXGFscGhhID0gMSQuIFBsb3QgeW91ciBvYnNlcnZhdGlvbnMuCgpgYGB7ciBHUCBzaW11bGF0aW9ufQoKTWF0ZXJuX2NvdiA8LSBmdW5jdGlvbihzaWdtYSwgcGhpLCB0KXsKICAgICMgcGFyYW0gc2lnbWE6IHNjYWxpbmcgY29lZgogICAgIyBwYXJhbSBldGE6IHJhbmdlIGNvZWYKICAgICMgcGFyYW0gdDogZGlzdGFuY2UgbWF0cml4CiAgICAjIHJldHVybjogbWF0ZXJuIGNvdmFyaWFuY2UKICAgIHJldHVybihzaWdtYSBeIDIgKiAoMSArIHBoaSAqIHQpICogZXhwKC1waGkgKiB0KSkKfQoKcGxvdGYgPC0gZnVuY3Rpb24odiwgc3RyaW5nKXsKICB2diA8LSB2CiAgZGltKHZ2KSA8LSBjKG4xLCBuMikKICBsZXZlbHBsb3QodnYsIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHN0cmluZykKfQoKIyBTZXR1cCB0aGUgZ3JpZApuMSA9IDI1ICMgbnVtYmVyIG9mIGdyaWQgcG9pbnRzIGFsb25nIGVhc3QgZGlyZWN0aW9uCm4yID0gMjUgIyBudW1iZXIgb2YgZ3JpZCBwb2ludHMgYWxvbmcgbm9ydGggZGlyZWN0aW9uCm4gPSBuMSAqIG4yICMgdG90YWwgbnVtYmVyIG9mIGdyaWQgcG9pbnRzCgpkbjEgPSAxL24xCmRuMiA9IDEvbjIKc2l0ZXMxID0gYXJyYXkoc2VxKDAsIDEsIGRuMSksIGMobjEsIDEpKQpzaXRlczIgPSBhcnJheShzZXEoMCwgMSwgZG4yKSwgYyhuMiwgMSkpCiMgc2l0ZXMxID0gYXJyYXkoc2VxKDEsIG4xKSwgYyhuMSwgMSkpCiMgc2l0ZXMyID0gYXJyYXkoc2VxKDEsIG4yKSwgYyhuMiwgMSkpCnd3MSA9IHJlcCgxLCBuMSkKd3cyID0gcmVwKDEsIG4yKQpzaXRlczFtID0gc2l0ZXMxICUqJSB0KHd3MSkgIyBzaXRlczFtIGlzIHRoZSBtYXRyaXggdmVyc2lvbiBvZiBzaXRlczEKc2l0ZXMybSA9IHd3MiAlKiUgdChzaXRlczIpCgpzaXRlczF2ID0gbWF0cml4KHNpdGVzMW0sIG5yb3cgPSBuLCBuY29sID0gMSkKc2l0ZXMydiA9IG1hdHJpeChzaXRlczJtLCBucm93ID0gbiwgbmNvbCA9IDEpCgpwbG90KHNpdGVzMXYsIHNpdGVzMnYpCgojIENvbXB1dGUgdGhlIGRpc3RhbmNlIG1hdHJpeApkZEUgPSBzaXRlczF2ICUqJSBtYXRyaXgocmVwKDEsIG4pLCBucm93ID0gMSwgbmNvbCA9IG4pIC0gbWF0cml4KHJlcCgxLCBuKSwgbnJvdyA9IG4sIG5jb2wgPSAxKSAlKiUgdChzaXRlczF2KQpkZDJFID0gZGRFICogZGRFCmRkTiA9IHNpdGVzMnYgJSolIG1hdHJpeChyZXAoMSwgbiksIG5yb3cgPSAxLCBuY29sID0gbikgLSBtYXRyaXgocmVwKDEsIG4pLCBucm93ID0gbiwgbmNvbCA9IDEpICUqJSB0KHNpdGVzMnYpCmRkMk4gPSBkZE4gKiBkZE4KdCA9IHNxcnQoZGQyRSArIGRkMk4pCmxldmVscGxvdCh0LCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiRGlzdGFuY2UgbWF0cml4IikKCiMgU2ltdWxhdGUgdGhlIGluaXRpYWwgcmFuZG9tIGZpZWxkCmFscGhhID0gMS4wICMgYmV0YSBhcyBpbiByZWdyZXNzaW9uIG1vZGVsCnNpZ21hID0gMS4wICAjIHNjYWxpbmcgY29lZiBpbiBtYXRlcm4ga2VybmVsCnBoaSA9IDEwICMgcmFuZ2UgY29lZiBpbiBtYXRlcm4ga2VybmVsCiMgZXRhID0gMTAgIyByYW5nZSBjb2VmIGluIG1hdGVybiBrZXJuZWwKdGF1ID0gLjA1ICMgaWlkIG5vaXNlCgpiZXRhMSA9IC1hbHBoYQpiZXRhMiA9IGFscGhhCmJldGEzID0gYWxwaGEKCkJFVEFfVFJVRSA9IG1hdHJpeChjKGJldGExLCBiZXRhMiwgYmV0YTMpLCBucm93ID0gMywgbmNvbCA9IDEpClRIRVRBX1RSVUUgPSBtYXRyaXgoYyhzaWdtYSwgcGhpLCB0YXUpLCBucm93ID0gMywgbmNvbCA9IDEpCgpTaWdtYSA9IE1hdGVybl9jb3Yoc2lnbWEsIHBoaSwgdCkgICMgbWF0ZXJuIGNvdmFyaWFuY2UKCkwgPSBjaG9sKFNpZ21hKSAjIGxvd2VyIEwKeCA9IHQoTCkgJSolIHJub3JtKG4pICMgc2FtcGxlIGZyb20gemVybyBtZWFuIHJhbmRvbSB2YXJpYWJsZXMKCkggPSBhcnJheShjKHJlcCgxLCBuKSwgc2l0ZXMxdiwgc2l0ZXMydiksIGRpbSA9IGMobiwgMykpICMgZGVzaWduIG1hdHJpeAptdV9wcmlvciA9IEggJSolIEJFVEFfVFJVRQpwbG90ZihtdV9wcmlvciwgInByaW9yIG1lYW4iKQptdV9yZWFsID0gbXVfcHJpb3IgKyB4CnBsb3RmKG11X3JlYWwsICJyZWFsaXNhdGlvbiBvZiB0aGUgZ3JmIikKCiMgc2FtcGxpbmcgZnJvbSByZWFsaXNhdGlvbnMKTSA9IDIwMApGbWF0cml4ID0gbWF0cml4KDAsIE0sIG4pCmluZCA9IHNhbXBsZShuLCBzaXplID0gTSwgcmVwbGFjZSA9IEZBTFNFKQpmb3IgKGkgaW4gYygxOk0pKXsKICBGbWF0cml4W2ksIGluZFtpXV0gPSBUUlVFCn0KRyA9IEZtYXRyaXggJSolIEgKeV9zYW1wbGVkID0gRm1hdHJpeCAlKiUgbXVfcmVhbCArIHRhdSAqIHJub3JtKE0sIDEpCnhfaW5kID0gc2l0ZXMxdltpbmRdCnlfaW5kID0gc2l0ZXMydltpbmRdCgpwbG90KHhfaW5kLCB5X2luZCwgY2V4ID0gYWJzKHlfc2FtcGxlZCksIG1haW4gPSAiUmFuZG9tIHNhbXBsZXMgaW4gdGhlIGZpZWxkLCBjaXJjbGUgc2l6ZSBpbmRpY2F0ZXMgdGhlIHJlbGF0aXZlIHZhbHVlIikKCmBgYAoKKioqCgojIyAyLjIgUGFyYW10ZXIgZXN0aW1hdGlvbgoKV2Ugd2lsbCBub3cgdXNlIHRoZSBzaW11bGF0ZWQgZGF0YSB0byBlc3RpbWF0ZSB0aGUgbW9kZWwgcGFyYW1ldGVycyAkXGFscGhhLCBcc2lnbWFeMiwgXHRhdV4yLCBccGhpJCB1c2luZyBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGlvbi4gSXRlcmF0ZSBiZXR3ZWVuIHRoZSB1cGRhdGUgZm9yIHRoZSBtZWFuIHBhcmFtZXRlciwgYW5kIHVwZGF0aW5nIHRoZSBjb3ZhcmlhbmNlIHBhcmFtZXRlcnMuIE1vbml0b3IgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gYXQgZWFjaCBzdGVwIG9mIHRoZSBhbGdvcml0aG0gdG8gY2hlY2sgY29udmVyZ2VuY2UuCgpgYGB7ciwgcGFyYW1ldGVyIGVzdGltYXRpb259CiMlJQpDX21hdHJpeCA8LSBmdW5jdGlvbih0aGV0YSl7CiAgc2lnbWEgPSB0aGV0YVsxXQogIHBoaSA9IHRoZXRhWzJdCiAgdGF1ID0gdGhldGFbM10KICBTaWdtYSA9IE1hdGVybl9jb3Yoc2lnbWEsIHBoaSwgdCkKICBDID0gRm1hdHJpeCAlKiUgU2lnbWEgJSolIHQoRm1hdHJpeCkgKyBkaWFnKE0pICogdGF1XjIKICByZXR1cm4oQykKfQoKCmRDX2RzaWdtYSA8LSBmdW5jdGlvbih0aGV0YSl7CiAgIyBzaWdtYSA9IHRoZXRhJHNpZ21hCiAgIyBwaGkgPSB0aGV0YSRwaGkKICAjIHRhdSA9IHRoZXRhJHRhdQogIHNpZ21hID0gdGhldGFbMV0KICBwaGkgPSB0aGV0YVsyXQogIHRhdSA9IHRoZXRhWzNdCiAgS20gPSBNYXRlcm5fY292KDEuMCwgcGhpLCB0KSAjIHQgaGVyZSBpcyB0aGUgZGlzdGFuY2UgbWF0cml4LCBIIGlzIHRoZSBkZXNpZ24gbWF0cml4LCBzaW1pbGFyIHRvIFgKICBkQ19kc2dtID0gRm1hdHJpeCAlKiUgS20gJSolIHQoRm1hdHJpeCkKICByZXR1cm4oZENfZHNnbSkKfQoKZENfZHBoaSA8LSBmdW5jdGlvbih0aGV0YSl7CiAgc2lnbWEgPSB0aGV0YVsxXQogIHBoaSA9IHRoZXRhWzJdCiAgdGF1ID0gdGhldGFbM10KICBLbiA9IHNpZ21hIF4gMiAqICgtcGhpICogdCkgKiBleHAoLXBoaSAqIHQpCiAgcmV0dXJuKEZtYXRyaXggJSolIEtuICUqJSB0KEZtYXRyaXgpKQp9CgpkQ19kdGF1IDwtIGZ1bmN0aW9uKHRoZXRhKXsKICByZXR1cm4oZGlhZyhNKSkKfQoKIyBVc2UgZmlzaGVyIHNjb3JpbmcgdG8gZmluZCBNTEUgcGFyYW1ldGVycwojIGJldGEgPSBucC56ZXJvcyhbMywgMV0pCmJldGEgPSBtYXRyaXgoYygtMi4xLCAzLjEsIC45KSwgbnJvdyA9IDMsIG5jb2wgPSAxKQp0aGV0YSA9IHJiaW5kKC4yNDUsIDkuMywgLjAwMykKTUFYX0lURVIgPSA1Ck5vX2l0ZXIgPSAwCmVwc2lsb24gPSAxMApCZXRhID0gbWF0cml4KDAsIG5yb3cgPSBNQVhfSVRFUiwgbmNvbCA9IDMpCkxpa2VsaWhvb2QgPSBtYXRyaXgoMCwgbnJvdyA9IE1BWF9JVEVSLCBuY29sID0gMSkKCndoaWxlIChOb19pdGVyIDwgTUFYX0lURVIgJiBlcHNpbG9uID4gLjAwMDEpewogICAgQyA9IENfbWF0cml4KHRoZXRhKQogICAgYmV0YSA9IHNvbHZlKHQoRykgJSolIHNvbHZlKEMsIEcpLCB0KEcpICUqJSBzb2x2ZShDLCB5X3NhbXBsZWQpKQogICAgIyBiZXRhID0gbnAubGluYWxnLnNvbHZlKG5wLmRvdChHLlQsIG5wLmxpbmFsZy5zb2x2ZShDLCBHKSksIG5wLmRvdChHLlQsIG5wLmxpbmFsZy5zb2x2ZShDLCB5X3NhbXBsZWQpKSkKICAgIEJldGFbTm9faXRlciwgXSA9IHQoYmV0YSkKICAgIHogPSB5X3NhbXBsZWQgLSBHICUqJSBiZXRhCiAgICBsaWsgPSAtTS8yICogbG9nKDIgKiBwaSkgLSAxLzIgKiBsb2coZGV0KEMpKSAtICAxLzIgKiB0KHopICUqJSBzb2x2ZShDLCB6KSAjIG90aGVyd2lzZSwgaXQgYmVjb21lcyBpbmYKICAgIExpa2VsaWhvb2RbTm9faXRlciwgXSA9IGxpawoKICAgICMgRmluZCBkQyovZHRoZXRhCiAgICBkQ19kU2dtID0gZENfZHNpZ21hKHRoZXRhKQogICAgZENfZFBoaSA9IGRDX2RwaGkodGhldGEpCiAgICBkQ19kVGF1ID0gZENfZHRhdSh0aGV0YSkKCiAgICB1X3NpZ21hID0gLTEvMiAqIHN1bShkaWFnKHNvbHZlKEMsIGRDX2RTZ20pKSkgKyAxLzIgKiB0KHopICUqJSBzb2x2ZShDLCBkQ19kU2dtICUqJSBzb2x2ZShDLCB6KSkKICAgIHVfZXRhID0gLTEgLyAyICogc3VtKGRpYWcoc29sdmUoQywgZENfZFBoaSkpKSArIDEgLyAyICogdCh6KSAlKiUgc29sdmUoQywgZENfZFBoaSAlKiUgc29sdmUoQywgeikpCiAgICB1X3RhdSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIGRDX2RUYXUpKSkgKyAxIC8gMiAqIHQoeikgJSolIHNvbHZlKEMsIGRDX2RUYXUgJSolIHNvbHZlKEMsIHopKQoKICAgIHUgPSByYmluZCh1X3NpZ21hLCB1X2V0YSwgdV90YXUpCgogICAgVjExID0gLTEvMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYxMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYxMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKICAgIFYyMSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYyMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYyMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKICAgIFYzMSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYzMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYzMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKCiAgICBWID0gbWF0cml4KGMoVjExLCBWMTIsIFYxMywgVjIxLCBWMjIsIFYyMywgVjMxLCBWMzIsIFYzMyksIG5yb3cgPSAzLCBuY29sID0gMykKICAgICMgcHJpbnQobGlrKQogICAgIyBwcmludChOb19pdGVyKQogICAgdGhldGFfbmV3ID0gdGhldGEgLSBzb2x2ZShWLCB1KSAgIyBoZXJlIGl0IGlzIG1pbnVzLCBidXQgaW4gdGhlIGJvb2ssIGl0IHNheXMgcGx1cywgbmVlZHMgdG8gYmUgcmVjaGVja2VkCiAgICBlcHNpbG9uID0gbm9ybSh0aGV0YV9uZXcgLSB0aGV0YSwgdHlwZSA9ICIyIikgLyBub3JtKGJldGEsIHR5cGUgPSAiMiIpCiAgICB0aGV0YSA9IHRoZXRhX25ldwogICAgcHJpbnQocGFzdGUoZXBzaWxvbiAsICIgLCBpdGVyIG5vIGlzICIsIE5vX2l0ZXIpKQogICAgTm9faXRlciA9IE5vX2l0ZXIgKyAxCn0KIyBwcmludChiZXRhKQojIHByaW50KEJFVEFfVFJVRSkKIyBwcmludCh0aGV0YSkKIyBwcmludChUSEVUQV9UUlVFKQoKcGxvdChjKDE6Tm9faXRlciksIExpa2VsaWhvb2QsIG1haW4gPSAibGlrZWxpaG9vZCBmdW5jdGlvbiIpCgojIGFscGhhaCA9IChzdW0obnAuYWJzKGJldGEpKSAvIDMpLnNxdWVlemUoKQp0aGV0YWggPSB0aGV0YQpzaWdtYWggPSB0aGV0YVsxXQpwaGloID0gdGhldGFbMl0KdGF1aCA9IHRoZXRhWzNdCmJldGFoID0gYmV0YQpiZXRhMSA9IGJldGFbMV0KYmV0YTIgPSBiZXRhWzJdCmJldGEzID0gYmV0YVszXQoKIyBwcmludCgnRXN0aW1hdGVkIHNpZ21hIGlzICcsIHNpZ21haCwgIlxuRXN0aW1hdGVkIGV0YSBpcyAiLCBldGFoLCBcCiMgICAgICAgIlxuRXN0aW1hdGVkIHRhdSBpcyAiLCB0YXVoLCAiXG5Fc3RpbWF0ZWQgYWxwaGEgaXMgIiwgYWxwaGFoKQpwcmludChjYXQoIlxuRXN0aW1hdGVkIHNpZ21hIGlzICIsIHJvdW5kKHNpZ21haCwgZGlnaXRzID0gMyksICI7IFRydWUgc2lnbWEgaXMgIiwgVEhFVEFfVFJVRVsxXSwgCiAgICAgICAgICAgICJcbkVzdGltYXRlZCBwaGkgaXMgIiwgcm91bmQocGhpaCwgZGlnaXRzID0gMiksICI7IFRydWUgcGhpIGlzICIsIFRIRVRBX1RSVUVbMl0sIAogICAgICAgICAgICAiXG5Fc3RpbWF0ZWQgdGF1IGlzICIsIHJvdW5kKHRhdWgsIGRpZ2l0cyA9IDUpLCAiOyBUcnVlIHRhdSBpcyAiLCBUSEVUQV9UUlVFWzNdLCAKICAgICAgICAgICAgIlxuRXN0aW1hdGVkIGJldGExIGlzICIsIHJvdW5kKGJldGExLCBkaWdpdHMgPSAyKSwgIjsgVHJ1ZSBiZXRhMSBpcyAiLCBCRVRBX1RSVUVbMV0sIAogICAgICAgICAgICAiXG5Fc3RpbWF0ZWQgYmV0YTIgaXMgIiwgcm91bmQoYmV0YTIsIGRpZ2l0cyA9IDIpLCAiOyBUcnVlIGJldGEyIGlzICIsIEJFVEFfVFJVRVsyXSwgCiAgICAgICAgICAgICJcbkVzdGltYXRlZCBiZXRhMyBpcyAiLCByb3VuZChiZXRhMywgZGlnaXRzID0gMiksICI7IFRydWUgYmV0YTMgaXMgIiwgQkVUQV9UUlVFWzNdKSkKCgpgYGAKCgoqKiogCgojIyAyLjMgS3JpZ2luZwoKV2Ugd2lsbCBub3cgdXNlIHRoZSBlc3RpbWF0ZWQgbW9kZWwgcGFyYW1ldGVycyB0byBwZXJmb3JtIGtyaWdpbmcgcHJlZGljdGlvbi4gUHJlZGljdCB2YXJpYWJsZXMgJHgocykkLCB3aGVyZSBwcmVkaWN0aW9ucyBzaXRlcyBsaWUgb24gYSByZWd1bGFyIGdyaWQgb2Ygc2l6ZSAyNXgyNSBmb3IgdGhlIHVuaXQgc3F1YXJlLiBWaXN1YWxpemUgdGhlIEtyaWdpbmcgc3VyZmFjZSBhbmQgdGhlIHByZWRpY3Rpb24gc3RhbmRhcmQgZXJyb3IuIENvbXBhcmUgd2l0aCB0aGUgdHJ1ZSBmaWVsZC4KCmBgYHtyLCBrcmlnaW5nfQpTaWdtYWggPSBNYXRlcm5fY292KHNpZ21haCwgcGhpaCwgdCkgIyBlc3RpbWF0ZWQgY292YXJpYW5jZSBtYXRyaXgKTGggPSBjaG9sKFNpZ21haCkKbWggPSBIICUqJSBiZXRhaCArIExoICUqJSBybm9ybShuKQpDaCA9IENfbWF0cml4KHRoZXRhaCkKeHAgPSBtaCArIFNpZ21haCAlKiUgdChGbWF0cml4KSAlKiUgc29sdmUoQywgKHlfc2FtcGxlZCAtIEZtYXRyaXggJSolIG1oKSkKcGxvdGYoeHAsICJwb3N0ZXJpb3IgbWVhbiIpClNpZ21hcCA9IFNpZ21haCAtIFNpZ21haCAlKiUgdChGbWF0cml4KSAlKiUgc29sdmUoQ2gsIEZtYXRyaXggJSolIFNpZ21haCkKIyBwbG90ZihTaWdtYXAsICJwb3N0ZXJpb3IgY292YXJpYW5jZSIpCmVzdGQgPSBzcXJ0KGRpYWcoU2lnbWFwKSkKcGxvdGYoZXN0ZCwgInBvc3RlcmlvciBzdGQiKQpNU0UgPSBzcXJ0KHN1bShhYnMoeHAgLSBtdV9yZWFsKSAqKiAyKSAvIG4pCnByaW50KHBhc3RlKCJUaGUgcHJlZGljdGlvbiBlcnJvciBpcyAiLCBNU0UpKQpgYGAKCioqKgoKIyBQYXJ0IElJSQoKCgoKCgoKCgoKCgo=